package io.huaguoguo.juc;


import cn.hutool.core.util.RandomUtil;

import java.util.*;

/**
 * @Title:
 * @Description:
 * @author: huaguoguo
 * @Date： 2021/5/19 10:23
 */
public class MyLRUCache<K, V> {


    private int initCapacity = 8;
    private int size;
    private Node<K, V>[] table;

    private Node<K, V> head;
    private Node<K, V> tail;

    static class Node<K, V> {
        private int hash;
        private K key;
        private V value;
        // 整体双向链表节点
        private Node<K, V> before;
        private Node<K, V> after;
        // slot上的单向链表节点
        private Node<K, V> next;

        public Node(int hash, K key, V value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Node<K, V> newNode(int hash, K key, V value) {
        Node<K, V> node = new Node<>(hash, key, value);
        // 追加到链表最后
        linkNodeLast(node);
        return node;
    }

    private void linkNodeLast(Node<K, V> node) {
        // 链表为空的情况
        if (head == null) {
            head = node;
            tail = node;
        }
        // 双向链接到尾部
        Node<K, V> last = tail;
        last.after = node;
        node.before = last;
        tail = node;
    }

    public MyLRUCache(int initCapacity) {
        if (initCapacity > 0) {
            this.initCapacity = initCapacity;
        }
        this.table = (Node<K, V>[]) new Node[this.initCapacity];
    }

    public void put(K key, V value) {
        putVal(hash(key), key, value);
        // 扩容
        if (++size > (table.length * 0.75)) {
            resize();
        }
    }

    public void putVal(int hash, K key, V value) {
        Objects.requireNonNull(key, "不允许插入null");
        int n = table.length;
        int i;
        Node<K, V> p = table[i = (n - 1) & hash];
        Node<K, V> currNode = newNode(hash, key, value);
        // 当前slot无节点，直接装进去
        if (p == null || key.equals(p.key)) {
            table[i] = currNode;
        } else {
            // 追加到链表next
            Node<K, V> e = p;
            while (e.next != null) {
                e = e.next;
            }
            e.next = currNode;
        }
    }


    public V get(K key) {
        Objects.requireNonNull(key, "不允许null key");
        int n = table.length;
        int i, h;
        Node<K, V> p = table[i = (n - 1) & (h = hash(key))];
        if (p == null) {
            return null;
        }
        while (p != null) {
            if (key.equals(p.key)) {
                return p.value;
            }
            p = p.next;
        }
        return null;
    }

    public int hash(K key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    public void resize() {
        int s = 16;
        while (size > (s * 0.75)) {
            s *= 2;
        }
        Node<K, V>[] oldTab = table;
        table = new Node[s];
        // 数据装进新tab
        Node<K, V> p = head;
        while (p != null) {
            // 断开单链
            p.next = null;
            resizePut(p);
            p = p.after;
        }
    }

    private void resizePut(Node<K, V> currNode) {
        int n = table.length;
        int i;
        Node<K, V> p = table[i = (n - 1) & currNode.hash];
        // 当前slot无节点，直接装进去
        if (p == null || currNode.key.equals(p.key)) {
            table[i] = currNode;
        } else {
            // 追加到链表next
            Node<K, V> e = p;
            while (e.next != null) {
                e = e.next;

            }
            e.next = currNode;
        }
    }

    public static void main(String[] args) {
        MyLRUCache<String, String> cache = new MyLRUCache<>(8);
        List<String> keys = new ArrayList<>();
        for (int i = 0; i < 100; i++) {
            String key = "link-" + RandomUtil.randomString(6);
            cache.put(key, String.valueOf(i));
            keys.add(key);
            System.out.println("put: " + key + " -> " + i);
        }

        for (String key : keys) {
            String value = cache.get(key);
            System.out.println("get: " + key + " -> " + value);
        }
    }


}
